package leetcode.year2021.month11;

// 538. 把二叉搜索树转换为累加树
public class _12_1ConvertBST538 {
  // 思路二，后续遍历过程中，返回当前遍历过的值得总和
  public TreeNode convertBST(TreeNode root) {
    dfs(root,0);
    return root;
  }

  private int dfs(TreeNode root, int preSum) {
    if (root == null){
      return preSum;
    }
    preSum = dfs(root.right, preSum);
    preSum += root.val;
    root.val = preSum;
    preSum = dfs(root.left,preSum);
    return preSum;
  }

//  // 后序遍历更新，维护一个遍历过的总和值（因为是搜索二叉树，后续遍历则是由大遍历到小）
//  int sum = 0;
//  public TreeNode convertBST(TreeNode root) {
//    if (root != null){
//      convertBST(root.right);
//      sum += root.val;
//      root.val = sum;
//      convertBST(root.left);
//    }
//    return root;
//  }



  /**
   * 538. 把二叉搜索树转换为累加树
   * 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），
   * 使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和（使得每个节点的值是原来的节点值加上所有大于它的节点值之和）。
   *
   * 提醒一下，二叉搜索树满足下列约束条件：
   *
   * 节点的左子树仅包含键 小于 节点键的节点。
   * 节点的右子树仅包含键 大于 节点键的节点。
   * 左右子树也必须是二叉搜索树。
   * 注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
   *
   *
   *
   * 示例 1：
   *
   *
   *
   * 输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
   * 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
   * 示例 2：
   *
   * 输入：root = [0,null,1]
   * 输出：[1,null,1]
   * 示例 3：
   *
   * 输入：root = [1,0,2]
   * 输出：[3,3,2]
   * 示例 4：
   *
   * 输入：root = [3,2,4,1]
   * 输出：[7,9,4,10]
   *
   *
   * 提示：
   *
   * 树中的节点数介于 0 和 104 之间。
   * 每个节点的值介于 -104 和 104 之间。
   * 树中的所有值 互不相同 。
   * 给定的树为二叉搜索树。
   */

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
      this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
}
